package Demo01;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;

public class Main {
    public static void main(String[] args) {
        String string = "abcabcbb";
        System.out.println(lengthOfLongestSubstring(string));
    }

    /**
     *
     * @param s
     * @param t 要蕴含的字符串
     * @return
     */
    public String minWindow(String s, String t) {
        if (s.length() < t.length()) {
            return "";
        }
        int[] count = new int[256];
        //负债记录
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            count[c]--;
        }
        int debt = t.length();
        int r = 0;
        int l = 0;
        int length = Integer.MAX_VALUE;
        int sLength = s.length();
        while (r<sLength) {
            char c = s.charAt(l);
            if(count[c]<0) {
                debt--;
            }
            count[c]++;
            if(debt==0) {
                //从后往前进行缩减数组
                while (count[s.charAt(l)]>0) {
                    l++;
                    count[s.charAt(l)]--;
                }
                length = length > (r-l+1) ? (r-l+1) : length;
            }
            r++;
        }
        return length==Integer.MAX_VALUE ? "" : s.substring(l, l+length);
    }

    public static int lengthOfLongestSubstring(String str) {
        char[] s = str.toCharArray();
        int n = s.length;
        int[] last = new int[256];
        Arrays.fill(last, -1);
        int ans = 0;
        int l = 0;
        int r = 0;
        while (r<n) {
            l = Math.max(l, last[s[r]+1]);
            ans = Math.max(ans, r-l+1);
            last[s[r]] = r;
            r++;
        }
        return ans;
    }

    public static int lengthOfLongestSubstring2(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        int length = 0;
        for (int l = 0, r = 0; r < s.length(); r++) {
            char c = s.charAt(r);
            if(map.containsKey(c)) {
                l = map.get(c);
                length = length > (r - l) ? length : (r - l);
            }
            map.put(c, r);
        }
        return length;
    }

    public static int lengthOfLongestSubstring1(String s) {
        HashSet<Character> set = new HashSet<>();
        int count = Integer.MAX_VALUE;
        for (int r = 0, l = 0; r < s.length(); r++) {
            char tmp = s.charAt(r);
            if(!set.contains(tmp)) {
                set.add(tmp);
            } else {
                count = count>(r-l)?(r-l):count;
                l = r;
            }
        }
        return count;
    }
}
